# 近似GCD(好题, 符合条件的连续子区间的个数, 1-based 前缀和 + 二分法查找)
from leetcode import test_function as tf


def sim_gcd_count_bf(arr, g):
    """我的方法, 一个优化的暴力算法, 通过/超时/总计 = 9/11/20,  通过率:45%
    主要利用两个指针, 如果左和右指针之间的区域不满足的数字大于等于2, 则左指针右移动
    """
    n = len(arr)
    res = 0
    illegal_ids = set()
    # 将不能整除的id加入非法列表
    for idx, num in enumerate(arr):
        if num % g != 0:
            illegal_ids.add(idx)

    for start in range(n - 1):
        count = 0
        if start in illegal_ids:
            count += 1
        for win_len in range(1, n - start + 1):  # 滑动窗口的大小
            if start + win_len in illegal_ids or start + win_len > n - 1:
                count += 1
            if count < 2:
                res += 1
            else:
                break
    return res


def sim_gcd_count_prefix(arr, g):
    """1-based前缀和 + 双指针
    通过/超时/总计 = 8/12/20, 通过率 = 40%
    我们把不是 g 的倍数的数标记成 1 ，把是 g 的倍数的数标记成 0。
    则问题被转化为求区间和小于等于 1 的区间个数。
    这样就可以使用前缀和的方法
    """
    n = len(arr)
    a = [0] * (n + 1)
    res = 0
    for i in range(1, n + 1):
        if arr[i - 1] % g != 0:
            a[i] = 1
        a[i] += a[i - 1]

    for i in range(1, n):
        j = 0
        for j in range(i + 1, n + 1):
            if a[j] - a[i - 1] > 1:
                break
        res += j - i - 1
    return res


def sim_gcd_count_bisect(arr, g):
    """1-based前缀和 + 二分查找的方法
    通过率 = 100%
    """
    n = len(arr)
    a = [0] * (n + 1)
    res = 0
    # 构建1-based前缀和
    # 在g=3时:
    # [1, 3, 6, 4, 10] -> a = [0, 1, 1, 1, 2, 3]
    # [1, 3, 6, 4, 9, 5, 12, 8] -> a = [0, 1, 1, 1, 2, 2, 3, 3, 4]
    # 这样的前缀和结构可以清晰地划分出每个满足条件的子数组的分界
    for i in range(1, n + 1):
        if arr[i - 1] % g != 0:
            a[i] = 1
        a[i] += a[i - 1]

    # 通过二分法查找以i为子数组的起点查找所有符合条件的子数组
    for i in range(1, n):
        """下面通过二分查找找到第一个大于a[i]的值, 该值通过l表示"""
        l, r = i + 1, n  # l表示子数组的终点, 由于子数组长度最少是2, 所以终点l至少是i+1, r=n表示中点最大可能到整个数组的末尾
        while l <= r:
            mid = (l + r) >> 1
            if a[mid] - a[i - 1] > 1:
                r = mid - 1
            else:
                l = mid + 1

        res += l - i - 1  # l - i- 1 是以i为起点, l为终点的子数组的个数

    return res


if __name__ == '__main__':
    # n, g = map(int, input().split())
    # inp_arr = list(map(int, input().split()))
    with open("../../data/2022_c.in", "r") as file:
        n, g = map(int, file.readline().split())
        inp_arr = list(map(int, file.readline().split()))
    inp = [{"arr": [1, 3, 6, 4, 10], "g": 3},
           {"arr": [1, 3, 6, 4, 9, 5, 12, 8], "g": 3},
           {"arr": [2] * 1000, "g": 2},
           {"arr": inp_arr, "g": g},
           ]
    out = [5,
           12,
           499500,
           4396693248,
           ]
    # tf(sim_gcd_count_bf, inp, out)
    # tf(sim_gcd_count_prefix, inp, out)
    tf(sim_gcd_count_bisect, inp, out)
